leetcode/1-100/42. 接雨水.md

https://leetcode-cn.com/problems/trapping-rain-water/

官方解法

func trap(height []int) (ans int) {
    n := len(height)
    if n == 0 {
        return 0
    }
    //获取左向max
    leftMax := make([]int, n)
    leftMax[0] = height[0]
    for index := 1; index < n; index++ {
        leftMax[index] = max(leftMax[index-1], height[index])
    }
    //获取右向max
    rightMax := make([]int, n)
    rightMax[n-1] = height[n-1]
    for index := n - 2; index >= 0; index-- {
        rightMax[index] = max(rightMax[index+1], height[index])
    }

    for key, h := range height {
        ans += min(leftMax[key], rightMax[key]) - h
    }
    return ans
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

吊车尾解法

func trap(height []int) (ret int) {
    mapData := make(map[int][]int)
    xLeft := -1
    xRight := -1
    //用单调性剪枝
    for key, hItem := range height {
        if key != 0 {
            if xLeft == -1 && hItem < height[key - 1] {
                xLeft = key - 1
                continue
            }
            if xLeft != -1 {
                if hItem > height[key - 1] {
                    xRight = max(xRight, key)
                }
            }
        }
    }
    //fmt.Printf("xLeft:%+v,xRight:%+v\n",xLeft, xRight)
    if xLeft < 0 || xRight < 0 {
        return 0
    }

    maxHeight := -1
    for key, heightItem := range height {
        if key < xLeft || key > xRight {
            continue
        }
        heightItem++
        maxHeight = max(maxHeight, heightItem)
        if _, ok := mapData[heightItem]; ok {
            mapData[heightItem] = append(mapData[heightItem], key)
            continue
        }
        mapData[heightItem] = []int{key}
    }

    //补充数据
    if maxHeight >= 2 {
        for i := maxHeight - 1; i >= 1; i-- {
            if _, ok := mapData[i]; ok {
                mapData[i] = append(mapData[i], mapData[i+1]...)
            } else {
                mapData[i] = mapData[i+1]
            }
        }
    }
    //fmt.Printf("mapData:%+v\n", mapData)
    //一层一层切掉
    for level := maxHeight; level >= 1; level-- {
        if len(mapData[level]) == 1 {
            continue
        }
        if len(mapData[level]) == 2 {
            ret += abs(mapData[level][0]-mapData[level][1]) - 1
            continue
        }
        maxNum := -1
        minNum := xRight
        for _, item := range mapData[level] {
            maxNum = max(maxNum, item)
            minNum = min(minNum, item)
        }
        ret += (maxNum - minNum - 1) - (len(mapData[level]) - 2)
    }
    return ret
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}